home *** CD-ROM | disk | FTP | other *** search
/ MPEG Toolkit / MPEG Toolkit.iso / os2 / mpegenc / src / psearch.c < prev    next >
C/C++ Source or Header  |  1997-01-01  |  20KB  |  829 lines
  1. /*===========================================================================*
  2.  * psearch.c                                     *
  3.  *                                         *
  4.  *    Procedures concerned with the P-frame motion search             *
  5.  *                                         *
  6.  * EXPORTED PROCEDURES:                                 *
  7.  *    SetPixelSearch                                 *
  8.  *    SetPSearchAlg                                 *
  9.  *    SetSearchRange                                 *
  10.  *    MotionSearchPreComputation                         *
  11.  *    PMotionSearch                                 *
  12.  *    PSearchName                                 *
  13.  *    PSubSampleSearch                             *
  14.  *    PLogarithmicSearch                             *
  15.  *                                         *
  16.  *===========================================================================*/
  17.  
  18. /*
  19.  * Copyright (c) 1993 The Regents of the University of California.
  20.  * All rights reserved.
  21.  *
  22.  * Permission to use, copy, modify, and distribute this software and its
  23.  * documentation for any purpose, without fee, and without written agreement is
  24.  * hereby granted, provided that the above copyright notice and the following
  25.  * two paragraphs appear in all copies of this software.
  26.  *
  27.  * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
  28.  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  29.  * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
  30.  * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31.  *
  32.  * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
  33.  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  34.  * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  35.  * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
  36.  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  37.  */
  38.  
  39. /*  
  40.  *  $Header: /n/picasso/users/keving/encode/src/RCS/psearch.c,v 1.4 1993/07/22 22:23:43 keving Exp keving $
  41.  *  $Log: psearch.c,v $
  42.  * Revision 1.4  1993/07/22  22:23:43  keving
  43.  * nothing
  44.  *
  45.  * Revision 1.3  1993/06/30  20:06:09  keving
  46.  * nothing
  47.  *
  48.  * Revision 1.2  1993/06/03  21:08:08  keving
  49.  * nothing
  50.  *
  51.  * Revision 1.1  1993/03/02  18:27:05  keving
  52.  * nothing
  53.  *
  54.  */
  55.  
  56.  
  57. /*==============*
  58.  * HEADER FILES *
  59.  *==============*/
  60.  
  61. #include "all.h"
  62. #include "mtypes.h"
  63. #include "frames.h"
  64. #include "search.h"
  65. #ifdef OS2
  66. /* @@@ FAT 8.3 convention */
  67. #include "prototyp.h"
  68. #else
  69. #include "prototypes.h"
  70. #endif
  71. #include "fsize.h"
  72.  
  73.  
  74. /*==================*
  75.  * STATIC VARIABLES *
  76.  *==================*/
  77.  
  78.     /* none */
  79.  
  80.  
  81. /*==================*
  82.  * GLOBAL VARIABLES *
  83.  *==================*/
  84.  
  85. int pixelFullSearch;
  86. int searchRange;
  87. int psearchAlg;
  88.  
  89.  
  90. /*===============================*
  91.  * INTERNAL PROCEDURE prototypes *
  92.  *===============================*/
  93.  
  94.  
  95. /*=====================*
  96.  * EXPORTED PROCEDURES *
  97.  *=====================*/
  98.  
  99. /*===========================================================================*
  100.  *
  101.  * PMotionSearch
  102.  *
  103.  *    compute the best P-frame motion vector we can
  104.  *    
  105.  *
  106.  * RETURNS:    TRUE        =    motion vector valid
  107.  *        FALSE        =    motion vector invalid; should code I-block
  108.  *
  109.  * PRECONDITIONS:    The relevant block in 'current' is valid (it has not
  110.  *            been dct'd).  Thus, the data in 'current' can be
  111.  *            accesed through y_blocks, cr_blocks, and cb_blocks.
  112.  *            This is not the case for the blocks in 'prev.'
  113.  *            Therefore, references into 'prev' should be done
  114.  *            through the struct items ref_y, ref_cr, ref_cb
  115.  *
  116.  * POSTCONDITIONS:    current, prev should be unchanged.
  117.  *            Some computation could be saved by requiring
  118.  *            the dct'd difference to be put into current's block
  119.  *            elements here, depending on the search technique.
  120.  *            However, it was decided that it mucks up the code
  121.  *            organization a little, and the saving in computation
  122.  *            would be relatively little (if any).
  123.  *
  124.  * NOTES:    the search procedure need not check the (0,0) motion vector
  125.  *        the calling procedure has a preference toward (0,0) and it
  126.  *        will check it itself
  127.  *
  128.  * SIDE EFFECTS:    none
  129.  *
  130.  *===========================================================================*/
  131. boolean
  132. PMotionSearch(currentBlock, prev, by, bx, motionY, motionX)
  133.     LumBlock currentBlock;
  134.     MpegFrame *prev;
  135.     int by;
  136.     int bx;
  137.     int *motionY;
  138.     int *motionX;
  139. {
  140.     /* CALL SEARCH PROCEDURE */
  141.  
  142.     switch(psearchAlg) {
  143.     case PSEARCH_SUBSAMPLE:
  144.         PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX);
  145.         break;
  146.     case PSEARCH_EXHAUSTIVE:
  147.         PLocalSearch(currentBlock, prev, by, bx, motionY, motionX,
  148.              0x7fffffff);
  149.         break;
  150.     case PSEARCH_LOGARITHMIC:
  151.         PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX);
  152.         break;
  153.     case PSEARCH_TWOLEVEL:
  154.         PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX,
  155.                 0x7fffffff);
  156.         break;
  157.     default:
  158.         fprintf(stderr, "ILLEGAL PSEARCH ALG:  %d\n", psearchAlg);
  159.         exit(1);
  160.     }
  161.  
  162.     return TRUE;
  163. }
  164.  
  165.  
  166. /*===========================================================================*
  167.  *
  168.  * SetPixelSearch
  169.  *
  170.  *    set the pixel search type (half or full)
  171.  *
  172.  * RETURNS:    nothing
  173.  *
  174.  * SIDE EFFECTS:    pixelFullSearch
  175.  *
  176.  *===========================================================================*/
  177. void
  178. SetPixelSearch(searchType)
  179.     char *searchType;
  180. {
  181.     if ( strcmp(searchType, "FULL") == 0 ) {
  182.     pixelFullSearch = TRUE;
  183.     } else if ( strcmp(searchType, "HALF") == 0 ) {
  184.     pixelFullSearch = FALSE;
  185.     } else {
  186.     fprintf(stderr, "ERROR:  Invalid pixel search type:  %s\n",
  187.         searchType);
  188.     exit(1);
  189.     }
  190. }
  191.  
  192.  
  193. /*===========================================================================*
  194.  *
  195.  * SetPSearchAlg
  196.  *
  197.  *    set the P-search algorithm
  198.  *
  199.  * RETURNS:    nothing
  200.  *
  201.  * SIDE EFFECTS:    psearchAlg
  202.  *
  203.  *===========================================================================*/
  204. void
  205. SetPSearchAlg(alg)
  206.     char *alg;
  207. {
  208.     if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
  209.     psearchAlg = PSEARCH_EXHAUSTIVE;
  210.     } else if (strcmp(alg, "SUBSAMPLE") == 0 ) {
  211.     psearchAlg = PSEARCH_SUBSAMPLE;
  212.     } else if ( strcmp(alg, "LOGARITHMIC") == 0 ) {
  213.     psearchAlg = PSEARCH_LOGARITHMIC;
  214.     } else if ( strcmp(alg, "TWOLEVEL") == 0 ) {
  215.     psearchAlg = PSEARCH_TWOLEVEL;
  216.     } else {
  217.     fprintf(stderr, "ERROR:  Invalid psearch algorithm:  %s\n", alg);
  218.     exit(1);
  219.     }
  220. }
  221.  
  222.  
  223. /*===========================================================================*
  224.  *
  225.  * PSearchName
  226.  *
  227.  *    returns a string containing the name of the search algorithm
  228.  *
  229.  * RETURNS:    pointer to the string
  230.  *
  231.  * SIDE EFFECTS:    none
  232.  *
  233.  *===========================================================================*/
  234. char *
  235. PSearchName()
  236. {
  237.     switch(psearchAlg) {
  238.     case PSEARCH_EXHAUSTIVE:
  239.         return "EXHAUSTIVE";
  240.     case PSEARCH_SUBSAMPLE:
  241.         return "SUBSAMPLE";
  242.     case PSEARCH_LOGARITHMIC:
  243.         return "LOGARITHMIC";
  244.     case PSEARCH_TWOLEVEL:
  245.         return "TWOLEVEL";
  246.     default:
  247.         exit(1);
  248.         break;
  249.     }
  250. }
  251.  
  252.  
  253. /*===========================================================================*
  254.  *
  255.  * SetSearchRange
  256.  *
  257.  *    sets the range of the search to the given number of pixels
  258.  *
  259.  * RETURNS:    nothing
  260.  *
  261.  * SIDE EFFECTS:    searchRange, fCode
  262.  *
  263.  *===========================================================================*/
  264. void
  265. SetSearchRange(pixels)
  266.     int pixels;
  267. {
  268.     searchRange = 2*pixels;    /* +/- 'pixels' pixels */
  269. }
  270.  
  271.  
  272. /*===========================================================================*
  273.  *
  274.  *                USER-MODIFIABLE
  275.  *
  276.  * MotionSearchPreComputation
  277.  *
  278.  *    do whatever you want here; this is called once per frame, directly
  279.  *    after reading
  280.  *
  281.  * RETURNS:    whatever
  282.  *
  283.  * SIDE EFFECTS:    whatever
  284.  *
  285.  *===========================================================================*/
  286. void
  287. MotionSearchPreComputation(frame)
  288.     MpegFrame *frame;
  289. {
  290.     /* do nothing */
  291. }
  292.  
  293.  
  294. /*===========================================================================*
  295.  *
  296.  * PSubSampleSearch
  297.  *
  298.  *    uses the subsampling algorithm to compute the P-frame vector
  299.  *
  300.  * RETURNS:    motion vector
  301.  *
  302.  * SIDE EFFECTS:    none
  303.  *
  304.  * REFERENCE:  Liu and Zaccarin:  New Fast Algorithms for the Estimation
  305.  *        of Block Motion Vectors, IEEE Transactions on Circuits
  306.  *        and Systems for Video Technology, Vol. 3, No. 2, 1993.
  307.  *
  308.  *===========================================================================*/
  309. int32
  310. PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX)
  311.     LumBlock currentBlock;
  312.     MpegFrame *prev;
  313.     int by;
  314.     int bx;
  315.     int *motionY;
  316.     int *motionX;
  317. {
  318.     register int mx, my;
  319.     int32 diff, bestBestDiff;
  320.     int        stepSize;
  321.     register int x;
  322.     int        bestMY[4], bestMX[4], bestDiff[4];
  323.     int        leftMY, leftMX;
  324.     int        rightMY, rightMX;
  325.  
  326.     stepSize = (pixelFullSearch ? 2 : 1);
  327.  
  328.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  329.  
  330.     if ( searchRange < rightMY ) {
  331.     rightMY = searchRange;
  332.     }
  333.  
  334.     if ( searchRange < rightMX ) {
  335.     rightMX = searchRange;
  336.     }
  337.  
  338.     for ( x = 0; x < 4; x++ ) {
  339.     bestMY[x] = 0;
  340.     bestMX[x] = 0;
  341.     bestDiff[x] = 0x7fffffff;
  342.     }
  343.  
  344.     /* do A pattern */
  345.     for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
  346.     if ( my < leftMY ) {
  347.         continue;
  348.     }
  349.  
  350.     for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
  351.         if ( mx < leftMX ) {
  352.         continue;
  353.         }
  354.  
  355.         diff = LumMotionErrorA(currentBlock, prev, by, bx, my, mx, bestDiff[0]);
  356.  
  357.         if ( diff < bestDiff[0] ) {
  358.         bestMY[0] = my;
  359.         bestMX[0] = mx;
  360.         bestDiff[0] = diff;
  361.         }
  362.     }
  363.     }
  364.  
  365.     /* do B pattern */
  366.     for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
  367.     if ( my < leftMY ) {
  368.         continue;
  369.     }
  370.  
  371.     for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
  372.         if ( mx < leftMX ) {
  373.         continue;
  374.         }
  375.  
  376.         diff = LumMotionErrorB(currentBlock, prev, by, bx, my, mx, bestDiff[1]);
  377.  
  378.         if ( diff < bestDiff[1] ) {
  379.         bestMY[1] = my;
  380.         bestMX[1] = mx;
  381.         bestDiff[1] = diff;
  382.         }
  383.     }
  384.     }
  385.  
  386.     /* do C pattern */
  387.     for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
  388.     if ( my < leftMY ) {
  389.         continue;
  390.     }
  391.  
  392.     for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
  393.         if ( mx < leftMX ) {
  394.         continue;
  395.         }
  396.  
  397.         diff = LumMotionErrorC(currentBlock, prev, by, bx, my, mx, bestDiff[2]);
  398.  
  399.         if ( diff < bestDiff[2] ) {
  400.         bestMY[2] = my;
  401.         bestMX[2] = mx;
  402.         bestDiff[2] = diff;
  403.         }
  404.     }
  405.     }
  406.  
  407.     /* do D pattern */
  408.     for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
  409.     if ( my < leftMY ) {
  410.         continue;
  411.     }
  412.  
  413.     for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
  414.         if ( mx < leftMX ) {
  415.         continue;
  416.         }
  417.  
  418.         diff = LumMotionErrorD(currentBlock, prev, by, bx, my, mx, bestDiff[3]);
  419.  
  420.         if ( diff < bestDiff[3] ) {
  421.         bestMY[3] = my;
  422.         bestMX[3] = mx;
  423.         bestDiff[3] = diff;
  424.         }
  425.     }
  426.     }
  427.  
  428.     /* first check old motion */
  429.     if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
  430.      (*motionX >= leftMX) && (*motionX < rightMX) ) {
  431.     bestBestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, 0x7fffffff);
  432.     } else {
  433.     bestBestDiff = 0x7fffffff;
  434.     }
  435.  
  436.     /* look at Error of 4 different motion vectors */
  437.     for ( x = 0; x < 4; x++ ) {
  438.     bestDiff[x] = LumMotionError(currentBlock, prev, by, bx,
  439.                  bestMY[x], bestMX[x], bestBestDiff);
  440.  
  441.     if ( bestDiff[x] < bestBestDiff ) {
  442.         bestBestDiff = bestDiff[x];
  443.         *motionY = bestMY[x];
  444.         *motionX = bestMX[x];
  445.     }
  446.     }
  447.  
  448.     return bestBestDiff;
  449. }
  450.  
  451.  
  452. /*===========================================================================*
  453.  *
  454.  * PLogarithmicSearch
  455.  *
  456.  *    uses logarithmic search to compute the P-frame vector
  457.  *
  458.  * RETURNS:    motion vector
  459.  *
  460.  * SIDE EFFECTS:    none
  461.  *
  462.  * REFERENCE:  MPEG-I specification, pages 32-33
  463.  *
  464.  *===========================================================================*/
  465. int32
  466. PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX)
  467.     LumBlock currentBlock;
  468.     MpegFrame *prev;
  469.     int by;
  470.     int bx;
  471.     int *motionY;
  472.     int *motionX;
  473. {
  474.     register int mx, my;
  475.     int32 diff, bestDiff;
  476.     int        stepSize;
  477.     int        leftMY, leftMX;
  478.     int        rightMY, rightMX;
  479.     int        tempRightMY, tempRightMX;
  480.     int        spacing;
  481.     int        centerX, centerY;
  482.     int        newCenterX, newCenterY;
  483.  
  484.     stepSize = (pixelFullSearch ? 2 : 1);
  485.  
  486.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  487.  
  488.     bestDiff = 0x7fffffff;
  489.  
  490.     /* grid spacing */
  491.     if ( stepSize == 2 ) {    /* make sure spacing is even */
  492.     spacing = (searchRange+1)/2;
  493.     if ( (spacing % 2) != 0 ) {
  494.         spacing++;
  495.     }
  496.     } else {
  497.     spacing = (searchRange+1)/2;
  498.     }
  499.     centerX = 0;
  500.     centerY = 0;
  501.  
  502.     while ( spacing >= stepSize ) {
  503.     newCenterY = centerY;
  504.     newCenterX = centerX;
  505.  
  506.     tempRightMY = rightMY;
  507.     if ( centerY+spacing+1 < tempRightMY ) {
  508.         tempRightMY = centerY+spacing+1;
  509.     }
  510.     tempRightMX = rightMX;
  511.     if ( centerX+spacing+1 < tempRightMX ) {
  512.         tempRightMX = centerX+spacing+1;
  513.     }
  514.  
  515.     for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
  516.         if ( my < leftMY ) {
  517.         continue;
  518.         }
  519.  
  520.         for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
  521.         if ( mx < leftMX ) {
  522.             continue;
  523.         }
  524.  
  525.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  526.  
  527.         if ( diff < bestDiff ) {
  528.             newCenterY = my;
  529.             newCenterX = mx;
  530.  
  531.             bestDiff = diff;
  532.         }
  533.         }
  534.     }
  535.  
  536.     centerY = newCenterY;
  537.     centerX = newCenterX;
  538.  
  539.     if ( stepSize == 2 ) {    /* make sure spacing is even */
  540.         if ( spacing == 2 ) {
  541.         spacing = 0;
  542.         } else {
  543.         spacing = (spacing+1)/2;
  544.         if ( (spacing % 2) != 0 ) {
  545.             spacing++;
  546.         }
  547.         }
  548.     } else {
  549.         if ( spacing == 1 ) {
  550.         spacing = 0;
  551.         } else {
  552.         spacing = (spacing+1)/2;
  553.         }
  554.     }
  555.     }
  556.  
  557.     /* check old motion -- see if it's better */
  558.     if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
  559.      (*motionX >= leftMX) && (*motionX < rightMX) ) {
  560.     diff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestDiff);
  561.     } else {
  562.     diff = 0x7fffffff;
  563.     }
  564.  
  565.     if ( bestDiff < diff ) {
  566.     *motionY = centerY;
  567.     *motionX = centerX;
  568.     } else {
  569.     bestDiff = diff;
  570.     }
  571.  
  572.     return bestDiff;
  573. }
  574.  
  575.  
  576. /*===========================================================================*
  577.  *
  578.  * PLocalSearch
  579.  *
  580.  *    uses local exhaustive search to compute the P-frame vector
  581.  *
  582.  * RETURNS:    motion vector
  583.  *
  584.  * SIDE EFFECTS:    none
  585.  *
  586.  *===========================================================================*/
  587. int32
  588. PLocalSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar)
  589.     LumBlock currentBlock;
  590.     MpegFrame *prev;
  591.     int by;
  592.     int bx;
  593.     int *motionY;
  594.     int *motionX;
  595.     int32 bestSoFar;
  596. {
  597.     register int mx, my;
  598.     int32 diff, bestDiff;
  599.     int        stepSize;
  600.     int        leftMY, leftMX;
  601.     int        rightMY, rightMX;
  602.     int        distance;
  603.     int        tempRightMY, tempRightMX;
  604.  
  605.     stepSize = (pixelFullSearch ? 2 : 1);
  606.  
  607.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  608.  
  609.     /* try old motion vector first */
  610.     if ( VALID_MOTION(*motionY, *motionX) ) {
  611.     bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
  612.  
  613.     if ( bestSoFar < bestDiff ) {
  614.         bestDiff = bestSoFar;
  615.     }
  616.     } else {
  617.     *motionY = 0;
  618.     *motionX = 0;
  619.  
  620.     bestDiff = bestSoFar;
  621.     }
  622.  
  623.     /* try a spiral pattern */    
  624.     for ( distance = stepSize; distance <= searchRange;
  625.       distance += stepSize ) {
  626.     tempRightMY = rightMY;
  627.     if ( distance < tempRightMY ) {
  628.         tempRightMY = distance;
  629.     }
  630.     tempRightMX = rightMX;
  631.     if ( distance < tempRightMX ) {
  632.         tempRightMX = distance;
  633.     }
  634.  
  635.     /* do top, bottom */
  636.     for ( my = -distance; my < tempRightMY;
  637.           my += max(tempRightMY+distance-stepSize, stepSize) ) {
  638.         if ( my < leftMY ) {
  639.         continue;
  640.         }
  641.  
  642.         for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
  643.         if ( mx < leftMX ) {
  644.             continue;
  645.         }
  646.  
  647.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  648.  
  649.         if ( diff < bestDiff ) {
  650.             *motionY = my;
  651.             *motionX = mx;
  652.             bestDiff = diff;
  653.         }
  654.         }
  655.     }
  656.  
  657.     /* do left, right */
  658.     for ( mx = -distance; mx < tempRightMX;
  659.           mx += max(tempRightMX+distance-stepSize, stepSize) ) {
  660.         if ( mx < leftMX ) {
  661.         continue;
  662.         }
  663.  
  664.         for ( my = -distance+stepSize; my < tempRightMY-stepSize;
  665.           my += stepSize ) {
  666.         if ( my < leftMY ) {
  667.             continue;
  668.         }
  669.  
  670.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  671.  
  672.         if ( diff < bestDiff ) {
  673.             *motionY = my;
  674.             *motionX = mx;
  675.             bestDiff = diff;
  676.         }
  677.         }
  678.     }
  679.     }
  680.  
  681.     return bestDiff;
  682. }
  683.  
  684.  
  685. /*===========================================================================*
  686.  *
  687.  * PTwoLevelSearch
  688.  *
  689.  *    uses two-level search to compute the P-frame vector
  690.  *    first does exhaustive full-pixel search, then looks at neighboring
  691.  *    half-pixel motion vectors
  692.  *
  693.  * RETURNS:    motion vector
  694.  *
  695.  * SIDE EFFECTS:    none
  696.  *
  697.  *===========================================================================*/
  698. int32
  699. PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar)
  700.     LumBlock currentBlock;
  701.     MpegFrame *prev;
  702.     int by;
  703.     int bx;
  704.     int *motionY;
  705.     int *motionX;
  706.     int32 bestSoFar;
  707. {
  708.     register int mx, my;
  709.     register int   loopInc;
  710.     int32 diff, bestDiff;
  711.     int        leftMY, leftMX;
  712.     int        rightMY, rightMX;
  713.     int        distance;
  714.     int        tempRightMY, tempRightMX;
  715.     int        xOffset, yOffset;
  716.  
  717.     /* exhaustive full-pixel search first */
  718.  
  719.     COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
  720.  
  721.     rightMY--;
  722.     rightMX--;
  723.  
  724.     /* try old motion vector first */
  725.     if ( VALID_MOTION(*motionY, *motionX) ) {
  726.     bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
  727.  
  728.     if ( bestSoFar < bestDiff ) {
  729.         bestDiff = bestSoFar;
  730.     }
  731.     } else {
  732.     *motionY = 0;
  733.     *motionX = 0;
  734.  
  735.     bestDiff = bestSoFar;
  736.     }
  737.  
  738.     rightMY++;
  739.     rightMX++;
  740.  
  741.     /* try a spiral pattern */    
  742.     for ( distance = 2; distance <= searchRange; distance += 2 ) {
  743.     tempRightMY = rightMY;
  744.     if ( distance < tempRightMY ) {
  745.         tempRightMY = distance;
  746.     }
  747.     tempRightMX = rightMX;
  748.     if ( distance < tempRightMX ) {
  749.         tempRightMX = distance;
  750.     }
  751.  
  752.     /* do top, bottom */
  753.     loopInc = max(tempRightMY+distance-2, 2);
  754.     for ( my = -distance; my < tempRightMY; my += loopInc ) {
  755.         if ( my < leftMY ) {
  756.         continue;
  757.         }
  758.  
  759.         for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
  760.         if ( mx < leftMX ) {
  761.             continue;
  762.         }
  763.  
  764.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  765.  
  766.         if ( diff < bestDiff ) {
  767.             *motionY = my;
  768.             *motionX = mx;
  769.             bestDiff = diff;
  770.         }
  771.         }
  772.     }
  773.  
  774.     /* do left, right */
  775.     loopInc = max(tempRightMX+distance-2, 2);
  776.     for ( mx = -distance; mx < tempRightMX; mx += loopInc ) {
  777.         if ( mx < leftMX ) {
  778.         continue;
  779.         }
  780.  
  781.         for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
  782.         if ( my < leftMY ) {
  783.             continue;
  784.         }
  785.  
  786.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  787.  
  788.         if ( diff < bestDiff ) {
  789.             *motionY = my;
  790.             *motionX = mx;
  791.             bestDiff = diff;
  792.         }
  793.         }
  794.     }
  795.     }
  796.  
  797.     /* now look at neighboring half-pixels */
  798.     my = *motionY;
  799.     mx = *motionX;
  800.  
  801.     rightMY--;
  802.     rightMX--;
  803.  
  804.     for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
  805.     for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
  806.         if ( (yOffset == 0) && (xOffset == 0) )
  807.         continue;
  808.  
  809.         if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
  810.          ((diff = LumMotionError(currentBlock, prev, by, bx,
  811.              my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
  812.         *motionY = my+yOffset;
  813.         *motionX = mx+xOffset;
  814.         bestDiff = diff;
  815.         }
  816.     }
  817.     }
  818.  
  819.     return bestDiff;
  820. }
  821.  
  822.  
  823. /*=====================*
  824.  * INTERNAL PROCEDURES *
  825.  *=====================*/
  826.  
  827.     /* none */
  828.  
  829.